package bfprt



func FindMinK(arr []int, K int) int {
	return Bfprt(arr, 0, len(arr)-1, K-1)
}

// 输入一个数组，返回第k小的数

func Bfprt(arr []int, L, R, K int) int {
	if L == R {return arr[L]}
	M := GetMedianOfMedians(arr, L, R)
	l, r := partition1(arr, L, R, M)
	if K >= l && K <= R {
		return arr[K]
	} else if K < l {
		return Bfprt(arr, L, l-1, K)
	} else {
		return Bfprt(arr, r+1, R, K)
	}
}

func partition1(arr []int, L, R, M int) (int, int) {
	less := L-1
	more := R+1
	cur := L
	for cur < more {
		if arr[cur] < M {
			swap(arr, less+1, cur)
			less++
			cur++
		} else if arr[cur] > M {
			swap(arr, cur, more-1)
			more--
		} else {
			cur++
		}
	}
	return less + 1, more - 1
}

func GetMedianOfMedians(arr []int, L, R int) int {
	size := R-L+1
	offset := 0
	if size % 5 != 0 {
		offset = 1
	}
	mArr := make([]int, size/5 + offset)
	for group:=0; group<len(mArr); group ++ {
		groupFirst := L + group*5
		mArr[group] = GetMedian(arr, groupFirst, min(R, groupFirst+4))
	}
	return Bfprt(mArr, 0, len(mArr)-1, len(mArr)/2)
}

func min(a, b int) int {
	if a > b {
		return b
	}
	return a
}

func GetMedian(arr []int, L, R int) int {
	InsertSort(arr, L, R)
	return arr[(R+L)/2]
}

func InsertSort(arr []int, L, R int){
	for i:=L+1; i<=R; i++ {
		for j:=i-1; j>=0 && arr[j] > arr[j+1]; j-- {
			swap(arr, j, j+1)
		}
	}
}


